#include <iostream>
using namespace std;
typedef struct Bitree
{
    int data;
    struct Bitree *lchild,*rchild;
} Node,*Tree;

void show_first(Tree T)
{
    if(T)
    {
        cout<<T->data<<" ";
        show_first(T->lchild);
        show_first(T->rchild);
    }
}

void show_mid(Tree T)
{
    if(T)
    {
        show_mid(T->lchild);
        cout<<T->data<<" ";
        show_mid(T->rchild);
    }
}

void show_last(Tree T)
{
    if(T)
    {
        show_last(T->lchild);
        show_last(T->rchild);
        cout<<T->data<<" ";
    }
}

void insertTree(Tree &T,int a)
{
    if(T==NULL)
    {
        Tree s=new Node;
        s->data=a;
        s->lchild=NULL;
        s->rchild=NULL;
        T=s;
    }
    else if(a<T->data)
        insertTree(T->lchild,a);
    else if(a>T->data)
        insertTree(T->rchild,a);
}

void creatTree(Tree &T)
{
    int n;
    cin>>n;
    int a;
    while(n--)
    {
        cin>>a;
        insertTree(T,a);
    }
}

int query(Tree T,int x)
{
    if(T==NULL)
        return 0;
    //这部不能省略，在结尾只用return 0代替，因为这样会导致结束不了。
    //至于为什么会输出0，是因为如果省略了对T==NULL的判断，递归调用仍然可以正常结束并返回结果。
    //这是因为在C++中，没有显式返回值的函数会返回一个未定义的值。
    //对于整数类型的函数，默认情况下会返回0。
    //因此，即使省略了T==NULL的判断，函数依然会在达到叶子节点时返回一个默认值0。
    if(x==T->data)
        return 1;
    else if(x<T->data)
        query(T->lchild,x);
    else if(x>T->data)
        query(T->rchild,x);
}

//先序遍历的非递归算法
#include <queue>
queue<Tree>v;
void show_first_no(Tree T)
{
    Tree p=T;
    while(p||!v.empty())
    {
        if(p)
        {
            v.push(p);
            p=p->lchild;
        }
        else
        {
            Tree q;
            q=v.front();
            v.pop();
            cout<<q->data<<" ";
            p=q->rchild;
        }
    }
}
#include <stack>
stack<Tree>s;
void show_mid_no(Tree T)
{
    Tree p=T;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->lchild;
        }
        else
        {
            Tree q=s.top();
            s.pop();
            cout<<q->data<<" ";
            p=q->rchild;
        }
    }
}
#include <queue>
queue<Tree>a;
void show_layer(Tree T)
{
    Tree p=T;
    a.push(p);
    while(!a.empty())
    {
        Tree s=a.front();
        cout<<s->data<<" ";
        a.pop();
        if(s->lchild)
            a.push(s->lchild);
        if(s->rchild)
            a.push(s->rchild);
    }
}

void changeLeftAndRight(Tree &T)
{
    Tree tmp;
    if(T)
    {
        tmp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=tmp;
        changeLeftAndRight(T->lchild);
        changeLeftAndRight(T->rchild);
    }
}

int deep(Tree T)
{
    if(T==NULL) return 0;
    else
    {
        int m=deep(T->lchild);
        int n=deep(T->rchild);
        if(m>n)
            return m+1;
        else return n+1;
    }
}


int leafNode(Tree T)
{
   if(T==NULL) return 0;
   if(T->lchild==NULL&&T->rchild==NULL)
    return 1;
   else return leafNode(T->lchild)+leafNode(T->rchild);
}

int NodeNumber_0(Tree T)
{
	int i=0;
	if(T)
	{
		if(T->lchild==NULL&&T->rchild==NULL)
		{
			i=1;
		}
		else
		{
			i=NodeNumber_0( T->lchild ) + NodeNumber_0( T->rchild );
		}
	}
	return i;
}
int NodeNumber_1(Tree T)
{
	int i=0;
	if(T)
	{
		if( (T->lchild==NULL&&T->rchild!=NULL) ||(T->lchild!=NULL&&T->rchild==NULL))
		{
			i=1+NodeNumber_1(T->lchild)+NodeNumber_1(T->rchild);
		}
		else
		{
			i=NodeNumber_1(T->lchild)+NodeNumber_1(T->rchild);
		}
	}
	return i;
}

int NodeNumber_2(Tree T)
{
	int i=0;
	if(T)
	{
		if((T->lchild!=NULL)&&(T->rchild!=NULL))
		{
			i=1+NodeNumber_2(T->lchild) + NodeNumber_2(T->rchild);
		}
		else
		{
			i= NodeNumber_2(T->lchild) + NodeNumber_2(T->rchild);
		}
	}
	return i;
}

int GetNodeNumK(Tree root,int k)//第k层节点个数
{
    if(!root||k<1)return 0;
    //应该还要确定k不大于最大的层数，应该在调用此函数之前确认这一点，这里不再判断
    if(k==1)return 1;
    return GetNodeNumK(root->lchild,k-1)+GetNodeNumK(root->rchild,k-1);
}

int judge_complete(Tree T)//判断是否为完全二叉树
{
    //这里借用之前的queue
    Tree p=T,s;
    v.push(p);
    int flag=0;
    while(!v.empty())
    {
        s=v.front();
        v.pop();
        if(s==NULL) flag=1;
        else
        {
            if(flag==1) return 0;//not
            v.push(s->lchild);
            v.push(s->rchild);
        }
    }
    return 1;
}
int main()
{
    Tree T=NULL;
    creatTree(T);//二叉树创建

    show_first(T);//先序遍历
    cout<<endl;
    show_mid(T);//中序遍历
    cout<<endl;
    show_last(T);//后序遍历
    cout<<endl;


    int x;
    cin>>x;
    cout<<query(T,x)<<endl;//查找
    cin>>x;
    cout<<query(T,x)<<endl;

    int k;
    cin>>k;
    insertTree(T,k);//新节点插入

    show_first(T);//先序遍历
    cout<<endl;
    show_mid(T);//中序遍历
    cout<<endl;
    show_last(T);//后序遍历
    cout<<endl;


    show_mid_no(T);//插入新节点后的中序遍历（非递归算法）
    cout<<endl;
    show_layer(T);//层次遍历,这个算法我还不够熟悉

    changeLeftAndRight(T);//左右子树互换
    cout<<endl;
    //show_layer(T);
    show_first(T);//先序遍历
    cout<<endl;
    show_mid(T);//中序遍历
    cout<<endl;
    show_last(T);//后序遍历
    cout<<endl;
    changeLeftAndRight(T);//左右子树互换

    //show_layer(T);
    show_first(T);//先序遍历
    cout<<endl;
    show_mid(T);//中序遍历
    cout<<endl;
    show_last(T);//后序遍历
    cout<<endl;

    int height=deep(T);
    cout<<height<<endl;

    int sum=leafNode(T);
    cout<<sum<<endl;

    //补充
    cout<<NodeNumber_0(T)<<endl;
    cout<<NodeNumber_1(T)<<endl;
    cout<<NodeNumber_2(T)<<endl;

    int j=judge_complete(T);
    if(j==1) cout<<"is complete tree"<<endl;
    else cout<<"not a complete tree"<<endl;
    return 0;
}
